#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cmath>
#include <vector>

#include <timer.h>
#include <util.h>

using namespace std;

/** NOTE: Esto tiene que ser una copia exacta de ej1.cpp */
class Encuesta {
public:
	Encuesta (int i) {
		vector<int> p1(i,0);
		M_confianza = new vector< vector<int> >(i, p1);
		M_desconfianza = new vector< vector<int> >(i, p1);
		this->n = i;
	};
	
	~Encuesta()	{
		delete M_confianza;
		delete M_desconfianza;
	};
	
	void opinar(int x, int y){
		if (y>0)
			(*M_confianza)[x-1][y-1] = 1;
		else
			(*M_desconfianza)[x-1][-y-1] = -1;
	};

	bool confia(int x, int y) const { return (*M_confianza)[x-1][y-1] == 1; } ;
	bool desconfia(int x, int y) const { return (*M_desconfianza)[x-1][y-1] == -1; } ;
	
	int numAgentes() const {
		return this->n;
	}
	
	private:
		// Matriz de confianza: 
		// x SÍ confía en y -->  M(x,y) =  1
		// x NO confía en y -->  M(x,y) = -1
		// sino M(x,y) = 0
	
		vector< vector<int> >* M_confianza;
		vector< vector<int> >* M_desconfianza;
		int n;
		
};

class Conjunto {
public:	
	Conjunto (int i) {
		this->S = new int[i];
		for (int j=0; j<i; j++)
			this->S[j]=0;		
		this->size = 0;
		n = i;
	};
	
	~Conjunto() {
		delete [] S;
	};

	int tamanio() {
		return this->size;
	};

	bool esta(int i) {
		return this->S[i-1];
	};
	
	void agregar(int i) {
		if (!esta(i)) {
			this->S[i-1] = 1;
			this->size++;
		}
	};
	
	void quitar(int i) {
		if (esta(i)) {		
			this->S[i-1] = 0;
			this->size--;
		}
	};
		
	void listar() {
		for (int i = 1; i<=n; i++)
			if (esta(i)) cout << "  " << i;
		cout << endl;
		};
	
	private:
		int* S;
		int size;	int n;
};

extern int resolver( Conjunto &, const Encuesta & );

/** Acá empieza el generador. **/
static int gMin = 1;
static int gMax = 100000;

void generarMejorCaso( ostream &salida ) {
	// Mejor caso, que todos los agentes desconfíen de si mismos en ese caso solo
	// tenemos que recorrer la rama sin agente, es decir, hace i llamadas recursivas
	// y por cada una realiza las llamadas a prometedor y no prometedor, prometedor
	// tarda siempre O(i) y no prometedor en el caso agente no confía en si mismo tarda O(1),
	// por lo tanto sería O(i^2)
	
	/* Versión vieja con salida a archivo
	for(int i = gMin; i <= gMax; i++) {
		salida << i << " " << i << endl;
		
		for(int j = 1; j <= i; j++) {
			salida << j << " " << (-j) << endl;
		}
	}
	
	salida << "0 0" << endl;
	*/
	
	Timer t;
	
	ofstream times( "t1-times-mejor.txt" );
	ofstream clocks( "t1-clocks-mejor.txt" );
	
	for(int i = gMin; i <= gMax; i++) {
		Encuesta E(i);
		Conjunto S(i);
		
		for(int j = 1; j <= i; j++) {
			E.opinar(j,-j);
		}
		
		t.comenzar();
		resolver(S, E);
		t.terminar();
	
		times << i << ' ' << t.getTiempo() << endl;
		clocks << i << ' ' << t.getCiclos() << endl;
	}
	
	
	//salida << "mejor caso" << endl;
}

void generarPeorCaso( ostream &salida ) {
	// Peor caso, n agentes y 0 encuestas, nunca poda nada  así que tiene que recorrer
	// todo el árbol O(2^i * i)
	
	Timer t;
	
	ofstream times( "t1-times-peor.txt" );
	ofstream clocks( "t1-clocks-peor.txt" );
	
	for(int i = gMin; i <= gMax; i++) {
		Encuesta E(i);
		Conjunto S(i);
		
		t.comenzar();
		resolver(S, E);
		t.terminar();
	
		times << i << ' ' << t.getTiempo() << endl;
		clocks << i << ' ' << t.getCiclos() << endl;
	}
	
	/* Versión con archivo de salida
	for(int i = gMin; i <= gMax; i++) {
		salida << i << " " << 0 << endl;
	}
	
	salida << "0 0" << endl;*/
	//salida << "peor caso" << endl;
}

void generarCasosAleatorios( ostream &salida ) {
	Timer t;
	
	ofstream times( "t1-times-aleatorio.txt" );
	ofstream clocks( "t1-clocks-aleatorio.txt" );
	
	srand( time( 0 ) );
	
	for(int i = gMin; i <= gMax; i++) {
		Encuesta E(i);
		Conjunto S(i);
		
		int encuestas = 0;
		for(int j = 1; j <= i; j++) {
			int encuestas_agente = rand() % i;
			
			for(int k = 1; k <= encuestas_agente; k++) {
				int agente;
				
				do {
					agente = (1 + rand() % i) * (rand() % 2 ? 1 : -1);
				} while((agente > 0 && E.confia(j, agente)) || (agente < 0 && E.desconfia(j, -agente)));
				
				E.opinar(j, agente);
				encuestas++;
			}
		}
#define DEBUG
#ifdef DEBUG
		cerr << "============" << endl;
		cerr << i << " " << encuestas << endl;
		
		for(int j = 1; j <= i; j++) {
			cerr << j << " => ";
			for(int k = 1; k <= i; k++) {
				if(E.confia(j,k)) {
					cerr << k << " ";
				}
				
				if(E.desconfia(j,k)) {
					cerr << -k << " ";
				}
			}
			
			cerr << endl;
		}
#endif
		
		t.comenzar();
		resolver(S, E);
		t.terminar();
	
		times << i << ' ' << t.getTiempo() << endl;
		clocks << i << ' ' << t.getCiclos() << endl;
	}
	//salida << "caso aleatorio" << endl;
}

bool establecerMaximo( const char *str ) {
	if ( !str2int( str, &gMax ) ) {
		cerr << "Máximo no reconocido, debe ser un número entero.\n";
		return false;
	}
	
	return true;
}

bool establecerMinimo( const char *str ) {
	if ( !str2int( str, &gMin ) ) {
		cerr << "Mínimo no reconocido, debe ser un número entero.\n";
		return false;
	}
	
	return true;
}
